Daniel Dadush
Abstract:
We give the first deterministic algorithm for solving the (1+eps) approximate Closest Vector Problem (CVP) on any n dimensional lattice and any norm in 2^O(n)(1+1/eps)^n time and 2^n poly(n) space. Our algorithm builds on the lattice point enumeration techniques of Micciancio and Voulgaris (STOC `10) and Dadush, Peikert and Vempala (FOCS `11), and gives an elegant, deterministic alternative to the ``AKS Sieve'' based algorithms for (1+eps)-CVP (Ajtai, Kumar, and Sivakumar; STOC `01 and CCC `02). Furthermore, assuming the existence of a poly(n)-space and 2^O(n) time algorithm for exact CVP in the l_2 norm, the space complexity of our algorithm can be reduced to polynomial.
Our main technical contribution is a method for ``sparsifying'' any input lattice while approximately maintaining its metric structure. To this end, we employ the idea of random sublattice restrictions, which was first employed by Khot (FOCS `03) for the purpose of proving hardness for Shortest Vector Problem (SVP) under l_p norms.
Joint work with Gábor Kun (Renyi Institute).